package com.zpark.frog;

import com.zpark.frog.Plant;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 讨厌的青蛙
 *  书P
 */
public class NastyFrog {
    public static void main(String[] args) {
        /*
            i、j：循环变量
            dX、dY：步长
            pX、pY：被踩踏的第一颗水稻的上一颗水稻的x与y坐标：
            steps：稻田里，搜索的路径上，青蛙可以跳的步数
            max：用于存放被踩踏水稻最多的哪条路径上，被踩踏的水稻数（青蛙的步数）
         */
        int i, j, dX, dY, pX, pY, steps, max = 2;
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入稻田的行数");
        int r = scan.nextInt();
        System.out.println("请输入稻田的列数");
        int c = scan.nextInt();
        System.out.println("请输入被踩踏的稻子数");
        int n = scan.nextInt();
        Plant[] plants = new Plant[n];
        for(i = 0; i < n; i++){
            plants[i] = new Plant();
            System.out.println("请输入第" + (i + 1) + "颗水稻的x坐标");
            plants[i].setX(scan.nextInt());
            System.out.println("请输入第" + (i + 1) + "颗水稻的y坐标");
            plants[i].setY(scan.nextInt());
        }
        System.out.println("排序前 -> " + Arrays.toString(plants));
        sort(plants);
        System.out.println("排序后 -> " + Arrays.toString(plants));
        // 开始查找逻辑
        for(i = 0; i < n - 1; i++){
            for(j = i + 1; j < n; j++){
                // 获得前两棵被踩踏的水稻之间的x、y方向上的步长
                dX = Math.abs(plants[j].getX() - plants[i].getX());
                dY = Math.abs(plants[j].getY() - plants[i].getY());
                // 获得第一颗被踩踏的水稻的上一颗水稻的x、y坐标
                pX = plants[i].getX() - dX;
                pY = plants[i].getY() - dY;
                // 如果pX、pY在稻田里，则改路径不正确，换下一条
                if(pX >= 1 && pX <= r && pY >= 1 && pY <= c)
                    continue;
                // 将x方向上过早跳出稻田的路径排查掉，换下一条
                pX = plants[i].getX() + (max - 1) * dX;
                if(pX < 1 || pX > r)
                    continue;
                // 将y方向上过早跳出稻田的路径排查掉，换下一条
                pY = plants[i].getY() + (max - 1) * dY;
                if(pY < 1 || pY > c)
                    continue;
                // 如果改路径没有被排查掉，就要计算出该条路径上，青蛙能跳的步数
                steps = searchPath(plants[j], dX, dY, r, c, plants);
                if (steps > max)
                    max = steps;
            }
        }
        if(max == 2)
            max = 0;
        System.out.println("被踩踏最多的哪条路径上，共有" + max + "颗水稻被踩踏。");
    }

    /**
     * 将水稻数组排序，排序规则：
     *  先按照x坐标从小到大排，
     *  如果x坐标相等，就按照y坐标从小到大排列
     * @param plants
     */
    private static void sort(Plant[] plants){
        // 声明一个用于交换的变量
        Plant swapPlant;
        // 冒泡排序
        for(int i = 0; i < plants.length - 1; i++){
            for(int j = i + 1; j < plants.length; j++){
                if(plants[i].compare(plants[i], plants[j]) > 0){
                    swapPlant = plants[i];
                    plants[i] = plants[j];
                    plants[j] = swapPlant;
                }
            }
        }
    }
    /**
     * 判断从secPlant看是，步长为dX，dY，最多能走几步
     * @param secPlant 起始水稻
     * @param dX x方向步长
     * @param dY y方向步长
     * @param r 水稻田行数
     * @param c 水稻田列数
     * @param plants 所有
     * @return 某一方向上，最多能走的步数
     */
    private static int searchPath(Plant secPlant, int dX, int dY, int r,
                                  int c, Plant[] plants){
        int steps = 2; // 起始点已经是被踩踏的第二棵水稻，故另steps为2。
        boolean flag;
        Plant plant = new Plant();
        plant.setX(secPlant.getX() + dX);
        plant.setY(secPlant.getY() + dY);
        while(plant.getX() <= r && plant.getX() >= 1 && plant.getY() <= c
                && plant.getY() >= 1){
            flag = false;
// 每一步都要踩到水稻才算合理，也就是下一步应该踩踏到一棵被踩踏到的数组
            for (Plant p : plants) {
                if (plant.getX() == p.getX() && plant.getY() == p.getY())
                {
                    flag = true;
                    break;
                }
            }
            if(!flag){
                break;
            }
            plant.setX(plant.getX() + dX);
            plant.setY(plant.getY() + dY);
            steps++;
        }
        return steps;
    }
}
